1. Field of the Invention
This invention relates generally to error location, and more particularly to parallel error correction code based error location and error locator polynomial root determination.
2. Description of the Related Art
As use of electronic data continues to increase, so do requirements for data storage reliability. To protect against errors in data storage, electronic data systems typically incorporate error detection and correction schemes, often referred to as Error Correcting Codes (ECC). ECC is common in data storage, such as magnetic disk storage, magnetic tape storage, and other non-volatile memory storage that stores data when power is disconnected from the system, such as Phase-change memory (PCM) or Flash memory. In general, when writing data to storage, ECC data is associated in some manner with the actual user data. For example, when using a non-volatile memory such as Flash memory, ECC data often is stored in the memory along with the actual user data.
FIG. 1 is an illustration showing a typical prior art non-volatile memory arrangement 100 utilizing ECC data for data reliability checking. As illustrated in FIG. 1, a non-volatile memory 100 generally comprises a plurality of memory blocks 102, which generally is the smallest portion of memory that can be erased. Each memory block 102 generally comprises a fixed plurality of pages 104, which is the smallest size element that can be written or read from the non-volatile memory 100. Each page 104 typically is logically divided into two areas: a main area 106 and a spare area 108. It is in the spare area 108 where typical non-volatile memory systems store ECC data, such as the ECC check bits 110 illustrated in FIG. 1. The ECC check bits 110 generally are generated as the user data is being written to the memory. When the data is later read from memory, the ECC check bits 110 are utilized to determine if errors are present in the data, and if so, where the errors are located.
FIG. 2 is an illustration showing a conventional error detection and location arrangement 200 in a non-volatile memory. The conventional error detection and location arrangement 200 typically includes a check code generator 204 coupled to an error locator polynomial generator 208, which is coupled to an error locator 212. In operation, read data 202 is provided to the check code generator 204 from memory. The read data 202 generally includes both user data and ECC check bits generated as described previously. The check code generator 204 generates a syndrome polynomial 206 using received the read data 202. In general, the check code generator 204 generates ECC check bits for the received user data and compares the generated ECC check bits to the ECC check bits stored with the user data. If the two ECC check bits are the same, no errors are present. If not, a syndrome polynomial 206 is generated based on the generated ECC check bits.
The syndrome polynomial 206 is a unique encoded indication of where the errors are located within the user data. However, to find the actual location of the errors the syndrome polynomial 206 needs to be decoded. To facilitate decoding, the syndrome polynomial 206 is provided to an error locator polynomial generator 208. The error locator polynomial generator 208 generates an error locator polynomial 210 based on the syndrome polynomial 206. In this manner, the error locator polynomial 210 can be used to determine the actual locations of the errors by determining the roots of the error locator polynomial 210.
Once the error locator polynomial 210 is generated, the error locator polynomial 210 is provided to an error locator 212, which effectively determines the roots of the error locator polynomial 21 0. Although several methods can be utilized to determine the roots of the error locator polynomial 210, the conventional method examines each bit location in the user data to determine if the location satisfies the constraints of the error locator polynomial 210. If it does, the particular bit location contains an error, and if not, the particular bit location does not contain an error. Hence, conventional error locator arrangements perform a sequential search of the data, examining one bit location at a time to determine if the particular bit location satisfies the error locator polynomial 210 and thus contains an error. Unfortunately, such a sequential search can take an inordinate amount of time depending on the size of the data. Basically, the amount of time required is the number of clock cycles required to scan all the addresses that the scheme is capable of correcting. For example, when using a 512 byte block, 8192 cycles typically are required to complete the scan.
In view of the foregoing, there is a need for methods and apparatuses that reduce the number of clock cycles required to determine the location of errors present in data. The method and apparatuses should provide increased efficiency without requiring increased clock frequency, which generally requires a very high frequency clock that may not be easily available for this purpose and may also be too fast a clock to properly execute the required logic. In addition, the methods and apparatuses should not require asynchronous logic, which greatly increases the logic requirements by up to fifty times the amount of logic. In addition, the depth of such logic can require many additional clock cycles for the results to stabilize, which of course leads to control difficulties.